package qjc.g_链表;

import com.链表.练习题.ListNode;

public class g5_环形链表II {
    /**
     * 初始化两个指针，h 为快指针，t 为慢指针，使用快慢指针法检测环，
     * 如果快指针和慢指针相遇，说明存在环，将慢指针重新指向链表的头节点，
     *  使用两个慢指针从头节点和相遇点同时移动，直到它们再次相遇
     */
    public ListNode detectCycle(ListNode head) {
        ListNode h = head, t = head;
        while (h != null && h.next != null){
            h = h.next.next;
            t = t.next;
            if(h == t){
                t = head;
                while (true){
                    if(h == t){
                        return t;
                    }
                    h = h.next;
                    t = t.next;
                }
            }
        }
        return null;
    }
}
